//
//  dynamic.hpp
//  labuladong
//
//  Created by 刘振舟 on 2023/8/2.
//

#ifndef dynamic_hpp
#define dynamic_hpp

#include <stdio.h>
#include <vector>
#include <queue>

using namespace std;

class DynamicSolution {
public:
    int coinChange(vector<int>& coins, int amount);
    
    vector<int> advantageCount(vector<int>& nums1, vector<int>& nums2) {
//        pair比较时先比较first，后比较second
        priority_queue<pair<int, int>> heap;
        int length = nums1.size();
        for (int i = 0; i < length; ++i) {
//            emplace参数为插入队列未构造前的元素，而push先构造后插入
            heap.emplace(nums2[i], i);
        }
        sort(nums1.begin(), nums1.end());
        int left = 0, right = length - 1;
        vector<int> res(length);
        
        while (!heap.empty()) {
            auto [val, index] = heap.top();
            heap.pop();
            if (nums1[right] > val) {
                res[index] = nums1[right];
                --right;
            } else {
                res[index] = nums1[left];
                ++left;
            }
        }
        return res;
    }
};

#endif /* dynamic_hpp */
